package daily.oct;

public class lc1039 {
    //这题好难，根本不会，deepseek全程讲解作答（使用动态规划思路）
    
    public int minScoreTriangulation(int[] values) {
        int n = values.length;
        // dp[i][j] 表示从顶点 i 到 j 形成的多边形的最低分数
        int[][] dp = new int[n][n];
        
        // 区间长度从 3 开始，因为至少需要 3 个点才能形成多边形
        for (int len = 3; len <= n; len++) {
            // i 是区间起点
            for (int i = 0; i <= n - len; i++) {
                // j 是区间终点
                int j = i + len - 1;
                // 初始化为最大值
                dp[i][j] = Integer.MAX_VALUE;
                
                // k 是中间点，将多边形 [i,j] 分割为 [i,k] 和 [k,j]
                for (int k = i + 1; k < j; k++) {
                    // 计算三部分的和：
                    // 1. 多边形 [i,k] 的分数
                    // 2. 多边形 [k,j] 的分数  
                    // 3. 当前三角形 (i,k,j) 的分数
                    int score = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j];
                    dp[i][j] = Math.min(dp[i][j], score);
                }
            }
        }
        
        return dp[0][n - 1];
    }
}